Much work has been done in the area of scheduling, as described by Peter Brucker, in Scheduling Algorithms, Springer-Verlag New York, Inc., Secaucus, N.J., 1995. Scheduling is considered in the database scenario by Bianca Schroeder, Mor Harchol-Balter, Arun Iyengar, Erich Nahum, Adam Wierman, “How to Determine a Good Multi-Programming Level for External Scheduling,” icde, p. 60, 22nd International Conference on Data Engineering (ICDE'06), 2006. Another work that describes scheduling in terms of multi-query optimization and operators is Sharaf, M. A., Chrysanthis, P. K., Labrinidis, A., and Pruhs, K. 2006, in “Efficient scheduling of heterogeneous continuous queries”, in Proceedings of the 32nd international Conference on Very Large Data Bases (Seoul, Korea, Sep. 12-15, 2006). A number of different metrics have been used for the purpose of scheduling.
In the offline setting, Kellerer showed that single machine scheduling to minimize flow time is NP-hard to approximate with a factor of Ω(n0.5−ψ)(Hans Kellerer, Thomas Tautenhahn, Gerhard J. Woeginger, “Approximability and nonapproximability results for minimizing total flow time on a single machine,” Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p. 418-426, May 22-24, 1996, Philadelphia, Pa., United States). Thus preemption seems to be essential to obtaining tractable versions for the flow time measure, as discussed by Chandra Chekuri, Sanjeev Khanna , An Zhu, “Algorithms for minimizing weighted flow time”, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p. 84-93, July 2001, Hersonissos, Greece. With preemption in the unweighted case, shortest remaining processing time (SRPT) gives the optimal total flow time on a single machine. Stefano Leonardi, Danny Raz, “Approximating total flow time on parallel machines”, Proceedings of the twentyninth annual ACM symposium on Theory of computing, p. 110-119, May 4-6, 1997, El Paso, Tex., United States, analyzed SRPT for the multiprocessor case and showed an O(min{log ψ, log m/n})—competitive character, where ψ is the ratio of the minimum to maximum job processing times and n and m indicate the number of jobs and number of machines respectively. Leonardi et al. further showed that no online algorithm can achieve a better competitive ratio. The weighted case is known to be NP-hard even on a single machine. Chekuri gives a semi-online algorithm for a single machine that is O(log2 P)—competitive. The algorithms are viewed as an offline algorithm providing an O(log2 P) approximation in an polynomial time. Chekuri et al. present a quasi-PTAS that gives (1+ψ)—approximation solution for any instance of weighted flow time for the uniprocessor preemptive case. Becchetti forwards an algorithm in the resource augmentation scenario, Highest Density First, that is O(1)-speed O(1) approximation solution for the problem of preemptive total flow. (Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., and Pruhs, K. 2001, “Online Weighted Flow Time and Deadline Scheduling,” in Proceedings of the 4th international Workshop on Approximation Algorithms For Combinatorial Optimization Problems and 5th international Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization (Aug. 18-20, 2001). M. X. Goemans, K. Jansen, J. D. Rolim, and L. Trevisan, Eds. Lecture Notes In Computer Science, vol. 2129. Springer-Verlag, London, 36-47.)
For the maximum flow, Bender proves that in the non-preemptive case, FIFO is optimal for one processor and has a (3-2/m)—competitive ratio in an online setting for m>1 number of processors. (Michael A. Bender, Soumen Chakrabarti, S. Muthukrishnan, “Flow and stretch metrics for scheduling continuous job streams,” Proceedings of the ninth annual ACMSIAM symposium on Discrete algorithms, p. 270-279, Jan. 25-27, 1998, San Francisco, Calif., United States). The metric of interested is the stretch metric which can be understood as a special case of the weighted flow case with the weights being inverse of the processing time. The stretch metric was first analyzed by Bender in the context of scheduling and proved that no online algorithm can approximate the max stretch to within a factor of O(n0.5−ψ) unless P=NP for the non-preemptive case. In a preemptive offline case, Bender et al. prove that a polynomial time algorithm exists that, for any fixed °, generates as output a schedule having max-flow at most 1+ψ times the optimum max-stretch. For the preemptive online max stretch problem Bender gives an algorithm that has a competitive ratio of O(ψ0.5). Bender's algorithm requires knowledge of the actual value of max stretch and is not sublinear in complexity. In a further development, Bender et al. give O(ψ0.5) competitive ratio algorithm for max stretch and has a much lower complexity then their previous work. (Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman, “Improved algorithms for stretch scheduling,” in Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p. 762-771, Jan. 6-8, 2002, San Francisco, Calif.). Maximum stretch is also considered in Legrand who provide a heuristic for the online multiprocessor case. (Legrand, A., Su, A., and Vivien, F., “Minimizing the stretch when scheduling flows of biological requests,” in Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (Cambridge, Mass., USA, Jul. 30-Aug. 2, 2006)). Bender et al. also provide a (1+ψ)—polynomial time approximation scheme for average stretch. S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes E. Gehrke, “Online Scheduling to Minimize Average Stretch”, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p. 433, Oct. 17-18, 1999 show that SRPT is 2-competitive for a uniprocessor case with respect to average stretch. In the same work Muthukrishnan et al. show that SRPT is 14-competitive for the multiprocessor case. Legrand et al. also give new bounds for sum-stretch. Luca Becchetti, Stefano Leonardi, S. Muthukrishnan, “Scheduling to minimize average stretch without migration,” Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p. 548-557, Jan. 9-11, 2000, San Francisco, Calif., United States discuss average stretch in the context of non-migration of jobs. Online scheduling is discussed extensively in Pruhs. (K. Pruhs, E. Torng and J. Sgall, “Online scheduling,” in Joseph Y.-T. Leung, Editor, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press (2004), pp. 15-1-15-41 (Chapter 15)). Another paradigm is stochastic online scheduling which is discussed in Megow. (Megow, N., Uetz, M., and Vredeveld, T. 2006. “Models and Algorithms for Stochastic Online Scheduling,” in Math. Oper. Res. 31, 3 (August 2006), 513-525). Semi-clairvoyant scheduling is discussed in Becchetti. (Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., and Pruhs, K. 2004. “Semi-clairvoyant scheduling,” in Theor. Comput. Sci. 324, 2-3 (September 2004), 325-335). Non-clairvoyant scheduling is considered in Bansal. (Bansal, N., Dhamdhere, K., and Sinha, A. 2004“Non-Clairvoyant Scheduling for Minimizing Mean Slowdown,” in Algorithmica 40, 4 (September 2004), 305-318). Various heuristics such as Most Requests First, First Come First Served, and Longest Wait First were considered in wireless context by Kalyan (Bala Kalyanasundaram, Kirk Pruhs, Mahendran Velauthapillai, “Scheduling Broadcasts in Wireless Networks,” in Proceedings of the 8th Annual European Symposium on Algorithms, p. 290-301, Sep. 5-8, 2000), in webservers by Friedman (Friedman, E. J. and Henderson, S. G. 2003. “Fairness and efficiency in web server protocols,” in Proceedings of the 2003 ACM SIGMETRICS international Conference on Measurement and Modeling of Computer Systems (San Diego, Calif., USA, Jun. 11-14, 2003). SIGMETRICS '03. ACM, New York, N.Y., 229-237) and Crovella (Crovella, M. E., Frangioso, R., and Harchol-Balter, M. 1999. “Connection scheduling in web servers,” in Proceedings of the 2nd Conference on USENIX Symposium on internet Technologies and Systems—Volume 2 (Boulder, Colo., Oct. 11-14, 1999). USENIX Association, Berkeley, Calif., 22-22). Another useful work is by Bedekar in the context of CDMA. (Bedekar, A., Borst, S. C., Ramanan, K., Whiting, P. A., and Yeh, E. M. 1999 “Downlink Scheduling in CDMA Data Networks,” in Technical Report. UMI Order Number: PNA-R9910., CWI (Centre for Mathematics and Computer Science)).